
import { TreeNode } from "./00_二叉搜索树BSTree";

class AVLTreeNode<T> extends TreeNode<T> {
    // 这里要对获取到的左节点右节点的类型进行重写，是AVLTreeNode
    left: AVLTreeNode<T> | null = null;
    right: AVLTreeNode<T> | null = null;
    parent: AVLTreeNode<T> | null = null;

    height: number = 1;

    // 获取每个节点的高度
    private getHeight(): number { 
        // 左子节点存在的话再去获得左子节点的高度
        const leftHeight = this.left? this.left.getHeight() : 0;
        const rightHeight = this.right? this.right.getHeight() : 0;
        // 找出左子节点和右子节点中较大的高度再加一就是平衡二叉树的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
    //权重: 平衡因子(左height - 右height)
    private getBalanceFactor(): number {
        const leftHeight = this.left? this.left.getHeight() : 0;
        const rightHeight = this.right? this.right.getHeight() : 0;

        return leftHeight - rightHeight;
    }

    // 直接判断当前节点是否平衡
    get isBalanced(): boolean {
        const factor = this.getBalanceFactor()
        return factor >= -1 && factor<= 1; // -1,0,1
    }
}

// 测试某个节点的高度

const av1Node1 = new AVLTreeNode(10)
av1Node1.right = new AVLTreeNode(15)
av1Node1.right.right = new AVLTreeNode(20)
// console.log(av1Node1.getHeight())
// console.log(av1Node1.right.getHeight())

// 测试平衡因子(权值)
// console.log(av1Node1.getBalanceFactor())
// console.log(av1Node1.right.getBalanceFactor())

console.log(av1Node1.isBalanced)
console.log(av1Node1.right.isBalanced)